﻿\documentclass{GangTimesBlog}
%=================正文=====================
\begin{document}
\maketitle
\par{
	\mytitle{算法原理}
	\mycontent
	{
	Logistic实际上是用Logistic函数实现二分类问题，在两个类很接近的边界上，Logistic函数十分陡峭，
	对于两个类的在边界上的区别十分敏感。从回归的角度解释，因变量是非度量变量，自变量是度量变量，
	这样的回归模型实则是一个阶梯函数；但是，阶梯函数不可微，失去了很多很好的性能，
	采用Logistic函数去逼近阶梯函数，从而实现回归，阶梯函数和Logistic函数的对比如下图所示，
	Logistic函数中的参数会影响函数的中间位置和陡峭程度。本文采用极大似然估计的方法建立凸优化模型，
	再用凸优化的分析和求解框架求解。
	}
	\begin{figure}[htpb]
		\centering
		\includegraphics[totalheight=6cm]{images/logistic2d.pdf}
		\caption{二维Logistic函数} 
		\label{fig:graph}
	\end{figure}

}
\par
{
	\mytitle{问题描述}
	\mycontent
	{
	二维空间类的一组坐标点$(x,y) \in {\bf{R}}^{2 \times n}$，这些点分为两类，引入$z \in \{0,1\}$，用于标识分类信息。
	在三维空间中对这些点进行描述，如下图所示。
	}
	\begin{figure}[htpb]
		\centering
		\includegraphics[totalheight=6cm]{images/createdata.pdf}
		\caption{两类二维离散样本点} 
		\label{fig:graph}
	\end{figure}
	\mycontent
	{
	通过建立三维空间中的Logistic函数，完成对上图所示样本的分类。对Logistic函数中待估参数的估计实则是一个回归分析过程。
	通过参数估计得到的Logistic函数又很好的实现了两类样本点的分类问题。所以，Logistic回归实际上是估计Logistic函数中的参数，
	并完成样本点的二分类问题。也就是说，Logistic回归实际上是一个二分类问题。
	}
}
\par
{
	\mytitle{优化模型}
	\mycontent
	{
	考虑随机变量$z \in \{0,1\}$，其概率密度为
		\begin{equation}
			{\bf{prob}}(z=1)=p,\quad\quad {\bf{prob}}(z=0)=1-p
		\end{equation}
	其中，$p \in[0,1]$，假定其由解释变量${\bm{u}}=\{x,y,1\}^T \in {\bf{R}}^{3 \times n}$决定。
	模型系数为${\bm{\theta}}=\{a,b,c\}^T \in {\bf{R}}^{3 \times n}	$，所以，Logistic模型具有如下形式
		\begin{equation}
			p=\frac{{\rm{exp}}({\bm{\theta}}^T {\bm{u}})}{1+{\rm{exp}}({\bm{\theta}}^T {\bm{u})}}
		\end{equation}
	Logistic模型决定了概率$p$和解释变量${\bm{u}}$之间的关系。\newline
	\indent 假定给定数据，包含解释变量${\bm{u}_1},...,{\bm{u}_m} \in {\bf{R}}^{3 \times n}$ 以及相应的输出
	$z_1,...,z_m \in \{0,1\}$的一组值。我们所要做的就是找到模型参数${\bm{\theta}} \in {\bf{R}}^{3 \times n}$的估计。
	本文采用极大似然估计的方法估计${\bm{\theta}}$的值，也称${\bm{\theta}}$的ML估计为Logistic回归。\newline
	\indent 求样本的联合概率，似然函数具有如下形式
		\begin{equation}
			\prod^m_{i=1}{p_i}^{z_i} (1-p_i)^{1-z_i}
		\end{equation}
	写成对数-似然函数的形式如下
		\begin{equation}
		\begin{split}
			 l({\bm{\theta}}) & =\sum^m_{i=1}({z_i}{\rm{log}}(p_i) +(1-z_i){\rm{log}}(1-p_i)) \\
				    & =\sum^m_{i=1}(z_i{\bm{\theta}}^T{\bm{u}_i}-{\rm{log}}(1+{\rm{exp}}({\bm{\theta}}^T {\bm{u}_i})))		
		\end{split}
		\end{equation}
	对数-似然函数$l({\bm{\theta}})$是关于变量${\bm{\theta}}$的凹函数，所以极大化对数-似然函数实际上是一个凸优化问题。
	根据已知的条件，建立求解Logistic中待估参数的凸优化模型如下所示：
		\begin{equation}
			\text{min} \ -l({\bm{\theta}}) \quad\quad \text{subject to}\quad {\bm{\theta}} \in {\bf{R}}^{3 \times n}
		\end{equation}
	将对数-似然函数代入得到优化模型如下：
		\begin{equation}
			\label{eq:optmodel}
			\text{min} \ f(\bm{\theta})= \sum^m_{i=1}({\rm{log}}(1+{\rm{exp}}({\bm{\theta}}^T {\bm{u}_i}))-z_i {\bm{\theta}}^T{\bm{u}_i}) \quad\quad \text{subject to}\quad {\bm{\theta}} \in {\bf{R}}^{3 \times n}
		\end{equation}
		
	}

}
\par
{
	\mytitle{优化求解}
	\mycontent
	{
	凸优化模型如公式 \eqref{eq:optmodel}所示，这是一个无约束凸优化问题，可以采取的求解算法很多。例如，最速下降法、Newton法、
	共轭梯度法、信赖域法、拟Newton法。本文采用Newton法进行优化模型的求解。Newton算法中主要有如下关键要素：\newline 
	\indent{\textbf{参数初值：}} 由于本文中的优化模型是凸优化模型，算法必然全局收敛；由于该模型是无约束优化模型，不需要考虑
	Newton初始参数的可行性问题，初始参数必然可行。 \newline 
	\indent{\textbf{停机准则：}} 停机准则可以采取梯度准则或者Newton减量。 \newline
	\indent{\textbf{步长选择：}} 若步长恒定为1，这是纯Newton方法。若采用一维搜索算法确定步长，是阻尼Newton方法。精确的一维搜索算法过于耗费计算成本，所以考虑不精确的一位搜索算法，
	只需要满足Wolfe条件即可。一种有效的算法是回溯直线法，回溯直线法得到的步长符合Wolfe条件，计算成本较低。 \newline
	\indent{\textbf{Newton步径：}} 如果Hessian矩阵正定，求解Newton方向是很容易的事。若Hessian矩阵不正定，
	就需要对Hessian矩阵进行适当的修正，使其正定。 \newline
	\indent 通过计算，求得目标函数的Jacobi矩阵如下所示：
		\begin{equation}
			J(\bm{\theta}) =\nabla_ {\bm{\theta}} f(\bm{\theta}) 
		\end{equation}
	\indent 通过计算，求得目标函数的Hessian矩阵如下所示：
	\begin{equation}
			H(\bm{\theta}) =\nabla_{\bm{\theta}}^2 f(\bm{\theta}) 
		\end{equation}
	\newline
	\fbox
	{
		\parbox{\textwidth}
		{ 
			\begin{flushleft}
			Newton方法框架如下：
				\begin{flalign}
				\begin{split}
				& \text{给定初始值}\bm{\theta} \in{\bf{R}}^{3 \times n} \text{，误差阈值}\epsilon \text{。} \\
				& \text{重复计算}  \\
				& \quad\quad \text{1.} \Delta \bm{\theta}_{nt}=-\nabla^2 f(\bm{\theta})^{-1}\nabla f(\bm{\theta});\quad \lambda^2=\nabla f(\bm{\theta})^T \nabla^2 f(\bm{\theta})^{-1}\nabla f(\bm{\theta}) \\
				& \quad\quad \text{2.} \text{停止准则：} \lambda^2 /2 \leq \epsilon \\
				& \quad\quad \text{3.} \text{直线搜索：回溯直线法，得到步长} \alpha_k \\
				& \quad\quad \text{4.} \text{改进：}\bm{\theta}=\bm{\theta}+\alpha_k \Delta \bm{\theta}_{nt} \\
				\end{split}
				\end{flalign}
			\end{flushleft}
		}
	}  
	}  
	

}
\par
{
	\mytitle{计算结果}
	\mycontent
	{
	通过生成一系列样本点${x_i,y_i,z_i}$，并在样本中加入了随机噪声。利用极大似然法则建立Logistic的无约束凸优化模型，应用Newton法计算
	优化模型的步径，应用回溯直线搜索求得满足Wolfe条件的步长。从系统辨识的角度理解，
	Logistic回归实际上是建立了一个Logistic函数作为系统模型，但是，参数未知，目的是要对Logistic函数的参数进行辨识。由于模型输出$z \in \{0,1\}$，
	所以，优化准则不能采取Euclid范数，也就是不能使用最小二乘。极大似然准则是基于似然函数极大化的准则，对样本分布没有限制，所以Logistic回归模型的建立
	应用了极大似然准则建立优化模型。由于对数-似然函数是一个凹函数，目标函数是极大化似然函数。可以将其转化为标准的凸优化模型，使得目标函数是
	极小化凹函数，这样就可以用凸优化的相关理论进行求解。通过Python编程，实现了二维数据点的Logistic分类，样本和分类结果如下图所示。
	}

	\begin{figure}[htpb]
	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[height=6cm]{images/logistic3d.pdf}
		\caption{分类实例1}
		\label{fig:side:a}
	\end{minipage}
	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[height=6cm]{images/logistic3d2.pdf}
		\caption{分类实例2}
		\label{fig:side:b}
	\end{minipage}
	\end{figure}
	
	\indent 本文程序的Python实现如下所示：
	
	\outpython{Logistic.py}

}
\end{document}